package org.sny.scramble;

import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.List;

public class Scramble {

	private static Hashtable<String, Integer> dictWords;
	private static List<String> words = new ArrayList<String>();
	
	public static void main(String[] args) {
		
		long start = System.currentTimeMillis();
		System.out.println("Solving...");
		
		dictWords = readDictionary();
		List<L> puzzle = generatePuzzle(
				"s", "i", "d", "v", 
				"p", "c", "r", "t",
				"t", "e", "a", "t",
				"e", "f", "w", "h");
		
		populate(puzzle.get(0), new ArrayList<L>());
		populate(puzzle.get(1), new ArrayList<L>());
		populate(puzzle.get(2), new ArrayList<L>());
		populate(puzzle.get(3), new ArrayList<L>());
		populate(puzzle.get(4), new ArrayList<L>());
		populate(puzzle.get(5), new ArrayList<L>());
		populate(puzzle.get(6), new ArrayList<L>());
		populate(puzzle.get(7), new ArrayList<L>());
		populate(puzzle.get(8), new ArrayList<L>());
		populate(puzzle.get(9), new ArrayList<L>());
		populate(puzzle.get(10), new ArrayList<L>());
		populate(puzzle.get(11), new ArrayList<L>());
		populate(puzzle.get(12), new ArrayList<L>());
		populate(puzzle.get(13), new ArrayList<L>());
		populate(puzzle.get(14), new ArrayList<L>());
		populate(puzzle.get(15), new ArrayList<L>());
		
		long end = System.currentTimeMillis();
		
		for(String word : words) {
			System.out.println(word);
		}
		
		System.out.println("Completed in " + (end - start) + " ms");
	}
	
	private static Hashtable<String, Integer> readDictionary() {
		Hashtable <String, Integer> dictWords = new Hashtable<String, Integer>(); 
		
		try{
			FileInputStream fstream = new FileInputStream("/Users/kdhindsa/Documents/workspace/scramble/src/dictionary.txt");
			DataInputStream in = new DataInputStream(fstream);
			BufferedReader br = new BufferedReader(new InputStreamReader(in));
			String strLine;
			while ((strLine = br.readLine()) != null)   {
				dictWords.put(strLine.toLowerCase(), strLine.length());
			}
			in.close();
		}
		catch (Exception e){
			System.err.println("Error: " + e.getMessage());
		}
		
		return dictWords;
	}
	
	/**
	 * Generate a puzzle based on the provided input letters in form of strings.
	 * c[x, y], means the letter at x+1th row and y+1th column.
	 * For example, c21 means the letter at 3rd row and 2nd column.
	 *  
	 * @param c00
	 * @param c01
	 * @param c02
	 * @param c03
	 * @param c10
	 * @param c11
	 * @param c12
	 * @param c13
	 * @param c20
	 * @param c21
	 * @param c22
	 * @param c23
	 * @param c30
	 * @param c31
	 * @param c32
	 * @param c33
	 * @return Reference to the top left letter (node) of the puzzle. l00, in this case.
	 */
	private static List<L> generatePuzzle(
			String c00, String c01, String c02, String c03,
			String c10, String c11, String c12, String c13,
			String c20, String c21, String c22, String c23,
			String c30, String c31, String c32, String c33) {
		
		// First row
		L l00 = new L(c00, "00");
		L l01 = new L(c01, "01");
		L l02 = new L(c02, "02");
		L l03 = new L(c03, "03");
		
		// Second row
		L l10 = new L(c10, "10");
		L l11 = new L(c11, "11");
		L l12 = new L(c12, "12");
		L l13 = new L(c13, "13");
		
		// Third row
		L l20 = new L(c20, "20");
		L l21 = new L(c21, "21");
		L l22 = new L(c22, "22");
		L l23 = new L(c23, "23");
		
		// Fourth row
		L l30 = new L(c30, "30");
		L l31 = new L(c31, "31");
		L l32 = new L(c32, "32");
		L l33 = new L(c33, "33");
		
		l00.setNeighbors(null, null, l01, l11, l10, null, null, null);
		l01.setNeighbors(null,  null,  l02,  l12,  l11,  l10,  l00,  null);
		l02.setNeighbors(null,  null,  l03,  l13,  l12,  l11,  l01,  null);
		l03.setNeighbors(null,  null,  null,  null, l13,  l12,  l02,  null);
		
		l10.setNeighbors(l00, l01, l11, l21, l20, null, null, null);
		l11.setNeighbors(l01, l02, l12, l22, l21, l20, l10, l00);
		l12.setNeighbors(l02, l03, l13, l23, l22, l21, l11, l01);
		l13.setNeighbors(l03, null, null, null, l23, l22, l12, l02);
		
		l20.setNeighbors(l10, l11, l21, l31, l30, null, null, null);
		l21.setNeighbors(l11, l12, l22, l32, l31, l30, l20, l10);
		l22.setNeighbors(l12, l13, l23, l33, l32, l31, l21, l11);
		l23.setNeighbors(l13, null, null, null, l33, l32, l22, l12);
		
		l30.setNeighbors(l20, l21, l31, null, null, null, null, null);
		l31.setNeighbors(l21, l22, l32, null, null, null, l30, l20);
		l32.setNeighbors(l22, l23, l33, null, null, null, l31, l21);
		l33.setNeighbors(l23, null, null, null, null, null, l32, l22);
		
		List<L> puzzle = new ArrayList<L>();
		puzzle.add(l00);
		puzzle.add(l01);
		puzzle.add(l02);
		puzzle.add(l03);
		puzzle.add(l10);
		puzzle.add(l11);
		puzzle.add(l12);
		puzzle.add(l13);
		puzzle.add(l20);
		puzzle.add(l21);
		puzzle.add(l22);
		puzzle.add(l23);
		puzzle.add(l30);
		puzzle.add(l31);
		puzzle.add(l32);
		puzzle.add(l33);
		
		return puzzle;
	}
	
	private static void populate(L l, List<L> w) {
		if(l == null) return;
		
		String wordSoFar = "";
		for(L n : w) {
			wordSoFar += n.getC();
		}
		
		if(dictWords.containsKey(wordSoFar + l.getC()) && !words.contains(wordSoFar + l.getC()))
			words.add(wordSoFar + l.getC());
		
		w.add(l);
		
		// check top
		if(!wordContains(w, l.getT())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getT(), w2);
		}
		
		// check right
		if(!wordContains(w, l.getR())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getR(), w2);
		}
		
		// check bottom
		if(!wordContains(w, l.getB())){
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getB(), w2);
		}
		
		// check left
		if(!wordContains(w, l.getL())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getL(), w2);
		}
		
		// check top left
		if(!wordContains(w, l.getTl())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getTl(), w2);
		}
		
		// check top right
		if(!wordContains(w, l.getTr())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getTr(), w2);
		}
		
		// check bottom left
		if(!wordContains(w, l.getBl())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getBl(), w2);
		}
		
		// check bottom right
		if(!wordContains(w, l.getBr())) {
			List<L> w2 = new ArrayList<L>();
			for(L n : w) {
				w2.add(n);
			}
			populate(l.getBr(), w2);
		}
		
	}
	
	static boolean wordContains(List<L> w, L l) {
		if(l == null) return false;
		
		for(L n : w) {
			if(n.getPos().equalsIgnoreCase(l.getPos()))
				return true;
		}
		return false;
	}
	
	// Class to represent one letter on the puzzle
	static class L {
		private String c; 	 // character (letter)
		private String pos;  // position in grid
		
		private L t; // top
		private L r; // right
		private L b; // bottom
		private L l; // left
		
		private L tl; // top left
		private L tr; // top right
		private L bl; // bottom left
		private L br; // bottom right
		
		L(String c, String pos){
			this.c = c;
			this.pos = pos;
		}
		
		public L getT() {
			return t;
		}

		public L getR() {
			return r;
		}

		public L getB() {
			return b;
		}

		public L getL() {
			return l;
		}

		public String getC() {
			return c;
		}

		public String getPos() {
			return pos;
		}
		
		public L getTl() {
			return tl;
		}

		public L getTr() {
			return tr;
		}

		public L getBl() {
			return bl;
		}

		public L getBr() {
			return br;
		}
		
		/**
		 * Set neighboring letters
		 * @param t Top
		 * @param tr Top-right
		 * @param r Right
		 * @param br Bottom-right
		 * @param b Bottom
		 * @param bl Bottom-left
		 * @param l Left
		 * @param tl Top-left
		 */
		public void setNeighbors(L t, L tr, L r, L br, L b, L bl, L l, L tl) {
			this.t = t;
			this.r = r;
			this.b = b;
			this.l = l;
			this.tl = tl;
			this.tr = tr;
			this.bl = bl;
			this.br = br;
		}
		
	}

}
